package 二叉树链式存储;

import javax.swing.tree.TreeNode;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree {
    static class BTNode {
        public int val;     // 代表节点的值
        public BTNode left; // 代表左孩子
        public BTNode right; // 代表右孩子

        public BTNode(int val) {
            this.val = val;
        }
    }
//    // 定义一个根节点
//    public BTNode root;

    public BTNode creatBinaryTree() {
        BTNode node1 = new BTNode(1);
        BTNode node2 = new BTNode(2);
        BTNode node3 = new BTNode(3);
        BTNode node4 = new BTNode(4);
        BTNode node5 = new BTNode(5);
        BTNode node6 = new BTNode(6);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        return node1;
    }

    // 前序遍历
    public void preOrder(BTNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历
    public void inOrder(BTNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    // 后序遍历
    public void postOrder(BTNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    // 获取树中节点的个数 (子问题思路：先算左子树节点数，再算右子树节点数，然后加上根节点)
    public int size(BTNode root) {
        if (root == null) {
            return 0;
        }
        int leftSize = size(root.left);
        int rightSize = size(root.right);
        return leftSize + rightSize + 1;
    }

    // 获取叶子节点的个数 （子问题思路：先算左子树有多少个叶子节点，再算右子树有几个叶子节点，最后相加）
    public int getLeafNodeCount(BTNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int leftCount = getLeafNodeCount(root.left);
        int rightCount = getLeafNodeCount(root.right);
        return leftCount + rightCount;
    }

    // 获取第K层节点的个数（先获取左子树的K-1层的节点数，然后获取右子树K-1层的节点数，然后相加）
    public int getKLevelNodeCount(BTNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        int leftNodeCount = getKLevelNodeCount(root.left, k - 1);
        int rightNodeCount = getKLevelNodeCount(root.right, k - 1);
        return leftNodeCount + rightNodeCount;
    }

    // 获取二叉树的高度
    public int getHeight(BTNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    // 检测值为value的元素是否存在(通过前序遍历，来寻找)
    public BTNode find(BTNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        BTNode ret = find(root.left, val);
        if (ret != null) {
            return ret;
        }
        ret = find(root.right, val);
        if (ret != null) {
            return ret;
        }
        return null;
    }

    //层序遍历
    public void levelOrder1(BTNode root) {
        Queue<BTNode> queue = new LinkedList<>();
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            System.out.println(root.val);
        }
        // 此时根节点不为空，左子树或右子树为空
        queue.offer(root);
        while (!queue.isEmpty()) {
            BTNode cur = queue.poll();       // 接收出队的节点
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }


    }


    // 层序遍历
    public List<List<Integer>> levelOrder(BTNode root) {
        List<List<Integer>> list = new LinkedList<>();
        if (root == null) {
            return list;
        }
        Queue<BTNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tmp = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                BTNode cur = queue.poll();

                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                tmp.add(cur.val);
            }
            list.add(tmp);
        }
        return list;
    }


    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(BTNode root) {

        return false;
    }


}
